#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-11-30 9:50 上午
# @Author  : yangdy
# @File    : 2020-11-30.767.重构字符串
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:

    class Heap:
        def __init__(self, data=None, key=None, reverse=False):
            self.data = data if data is not None else []
            self.key = key
            self.reverse = reverse
            if len(self.data) > 0:
                for i in range(len(self.data)//2, len(self.data)):
                    self.down(i)

        def _cmp(self, x, y):
            if self.key:
                x, y = self.key(x), self.key(y)
            return x < y if not self.reverse else x > y

        def clear(self):
            self.data = []

        def down(self, index=0):
            if index * 2 + 1 >= len(self.data):
                return
            x, y, ll = index * 2 + 1, index * 2 + 2, len(self.data)
            u = x if y >= ll or self._cmp(self.data[y], self.data[x]) else y
            if self._cmp(self.data[index], self.data[u]):
                self.data[u], self.data[index] = self.data[index], self.data[u]
                self.down(u)

        def up(self, index=0):
            if index <= 0:
                return
            x = index // 2
            if self._cmp(self.data[x], self.data[index]):
                self.data[x], self.data[index] = self.data[index], self.data[x]
                self.up(x)

        def top(self):
            return self.data[0] if len(self.data) > 0 else None

        def is_empty(self):
            return len(self.data) <= 0

        def insert(self, x):
            self.data.append(x)
            self.up(len(self.data)-1)

        def pop(self):
            if self.is_empty():
                return
            ans = self.data[0]
            last = self.data.pop()
            if not self.is_empty():
                self.data[0] = last
                self.down()
            return ans

    def reorganizeString(self, S: str) -> str:
        import collections
        c = collections.Counter(S)
        heap = self.Heap(key=lambda x: x[1])
        # heap.clear()
        for ci in c:
            heap.insert((ci, c[ci]))
        # while not heap.is_empty():
        #     print(heap.pop())
        ans = ''
        if heap.is_empty() or heap.top()[1] > (len(S)+1)//2:
            return ans
        while not heap.is_empty():
            x = heap.pop()
            y = heap.pop()
            if not ans or ans[-1] != x[0]:
                ans += x[0] + (y[0] if y else '')
            else:
                ans += (y[0] if y else '') + x[0]
            if x[1] > 1:
                heap.insert((x[0], x[1]-1))
            if y and y[1] > 1:
                heap.insert((y[0], y[1]-1))
        return ans

        # import collections
        #
        # c = collections.Counter(S)
        # if c[max(c, key=lambda x: c[x])] > (len(S)+1)//2:
        #     return ''
        # odd, even = 1, 0
        # ans_list = ['' for i in range(len(S))]
        # for ci in c:
        #     cc = c[ci]
        #     while 0 < cc <= len(S)//2 and odd < len(ans_list):
        #         ans_list[odd] = ci
        #         odd += 2
        #         cc -= 1
        #     while cc > 0:
        #         ans_list[even] = ci
        #         even += 2
        #         cc -= 1
        # return ''.join(ans_list)


questions = [
    ('aab',),
    ('aaab',),
    ('bbaaa',),
    ("vvvlo",),
]

work(questions, lambda q: Solution().reorganizeString(q[0]))
